home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Practical Algorithms for Image Analysis
/
Practical Algorithms for Image Analysis.iso
/
CH_6.1
/
XVOR
/
VOR.C
< prev
next >
Wrap
C/C++ Source or Header
|
1999-09-11
|
4KB
|
143 lines
/*
* vor.c
*
* Practical Algorithms for Image Analysis
*
* Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
*/
/*
* VOR.C
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "vor.h"
#undef DEBUG_VOR
/*
* voronoi()
* DESCRIPTION:
* voronoi analysis on a site
* implicit parameters:
* nsites, sqrt_nsites,
* xmin, xmax, ymin, ymax, deltax, deltay (can all be estimates).
* performance suffers if they are wrong;
* better to make nsites, deltax, and deltay too big than too small.
* ARGUMENTS:
* nextsite: site on which to do voronoi analysis (struct Site *)
* imgIO: image for drawing (Image *)
* value: grayscale value for drawing (int)
* RETURN VALUE:
* none
*/
void
voronoi (nextsite, imgIO, value)
struct Site *(*nextsite) ();
Image *imgIO;
int value;
{
struct Site *newsite, *bot, *top, *temp, *p;
struct Site *v;
struct Point newintstar;
int pm;
struct Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;
struct Edge *e;
#ifdef DEBUG_VOR
printf ("\n...VORONOI:\n");
printf (" parameters: nsites: %4d\n", nsites);
printf (" extrema: %f %f %f %f\n", xmin, xmax, ymin, ymax);
printf ("delx, dely: %f %f\n", deltax, deltay);
#endif
PQinitialize ();
bottomsite = (struct Site *) (*nextsite) ();
out_site (bottomsite, imgIO, value);
ELinitialize ();
newsite = (struct Site *) (*nextsite) ();
while (1) {
#ifdef DEBUG_VOR
printf ("...VORONOI: processing site %f %f\n",
newsite->coord.x, newsite->coord.y);
#endif
if (PQempty () == 0)
newintstar = PQ_min ();
if ((newsite != (struct Site *) NULL)
&& (PQempty ()
|| newsite->coord.y < newintstar.y
|| (newsite->coord.y == newintstar.y
&& newsite->coord.x < newintstar.x))) { /* new site is smallest */
out_site (newsite, imgIO, value);
lbnd = ELleftbnd (&(newsite->coord));
rbnd = ELright (lbnd);
bot = rightreg (lbnd);
e = bisect (bot, newsite, imgIO, value);
bisector = HEcreate (e, le);
ELinsert (lbnd, bisector);
if ((p = intersect (lbnd, bisector)) != (struct Site *) NULL) {
PQdelete (lbnd);
PQinsert (lbnd, p, dist (p, newsite));
}
lbnd = bisector;
bisector = HEcreate (e, re);
ELinsert (lbnd, bisector);
if ((p = intersect (bisector, rbnd)) != (struct Site *) NULL) {
PQinsert (bisector, p, dist (p, newsite));
}
newsite = (struct Site *) (*nextsite) ();
}
else if (!PQempty ()) { /* intersection is smallest */
lbnd = PQextractmin ();
llbnd = ELleft (lbnd);
rbnd = ELright (lbnd);
rrbnd = ELright (rbnd);
bot = leftreg (lbnd);
top = rightreg (rbnd);
out_triple (bot, top, rightreg (lbnd));
v = lbnd->vertex;
makevertex (v);
endpoint (lbnd->ELedge, lbnd->ELpm, v, imgIO, value);
endpoint (rbnd->ELedge, rbnd->ELpm, v, imgIO, value);
ELdelete (lbnd);
PQdelete (rbnd);
ELdelete (rbnd);
pm = le;
if (bot->coord.y > top->coord.y) {
temp = bot;
bot = top;
top = temp;
pm = re;
}
e = bisect (bot, top, imgIO, value);
bisector = HEcreate (e, pm);
ELinsert (llbnd, bisector);
endpoint (e, re - pm, v, imgIO, value);
deref (v);
if ((p = intersect (llbnd, bisector)) != (struct Site *) NULL) {
PQdelete (llbnd);
PQinsert (llbnd, p, dist (p, bot));
}
if ((p = intersect (bisector, rrbnd)) != (struct Site *) NULL) {
PQinsert (bisector, p, dist (p, bot));
}
}
else {
break;
}
}
for (lbnd = ELright (ELleftend); lbnd != ELrightend; lbnd = ELright (lbnd)) {
e = lbnd->ELedge;
out_ep (e, imgIO, value);
}
}